package skewreduce.lib;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class ChunkedList<E extends ITuple> implements List<E> {
	private ArrayList<List<E>> lists;
	private final int CHUNK_SIZE;
	private List<E> tail;
	private int numElem;
	
	public ChunkedList() {
		this(4096);
	}
		
	public ChunkedList(int chunkSize) {
		CHUNK_SIZE = chunkSize;
		lists = new ArrayList<List<E>>(CHUNK_SIZE);
		tail = new ArrayList<E>(CHUNK_SIZE);
		lists.add(tail);
	}

	@Override
	public boolean add(E e) {
		if ( tail.size() >= CHUNK_SIZE ) {
			tail = new ArrayList<E>(CHUNK_SIZE);
			lists.add(tail);
		}
		tail.add(e);
		++numElem;
		return true;
	}

	@Override
	public void add(int index, E element) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
		for ( E e : c ) {
			add(e);
		}
		return true;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public void clear() {
		lists.clear();
		tail = new ArrayList<E>(CHUNK_SIZE);
		lists.add(tail);
		numElem = 0;		
	}

	@Override
	public boolean contains(Object o) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public E get(int index) {
		int idx = index / CHUNK_SIZE;
		int off = index % CHUNK_SIZE;
		return lists.get(idx).get(off);
	}

	@Override
	public int indexOf(Object o) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean isEmpty() {
		return numElem == 0;
	}
	
	@Override
	public Iterator<E> iterator() {
		return new ChunkListIterator(0);
	}

	@Override
	public int lastIndexOf(Object o) {
		throw new UnsupportedOperationException();
	}

	@Override
	public ListIterator<E> listIterator() {
		return listIterator(0);
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		return new ChunkListIterator(index);
	}

	@Override
	public boolean remove(Object o) {
		throw new UnsupportedOperationException();
	}

	@Override
	public E remove(int index) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	@Override
	public E set(int index, E element) {
		int idx = index / CHUNK_SIZE;
		int off = index % CHUNK_SIZE;
		return lists.get(idx).set(off, element);
	}

	@Override
	public int size() {
		return numElem;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		throw new UnsupportedOperationException();
	}

	@Override
	public Object[] toArray() {
		Object[] tmp = new Object[numElem];
		int i = 0;
		for ( List<E> l : lists ) {
			Object[] src = l.toArray();
			System.arraycopy(src, 0, tmp, i, src.length);
			i += src.length;
		}
		return tmp;
	}

	@Override
	public <T> T[] toArray(T[] a) {
		T[] tmp = a;
		if ( tmp.length < numElem ) {
			tmp = Arrays.copyOf(a, numElem);
		}
		T[] buf = Arrays.copyOf(a, CHUNK_SIZE);
		int i = 0;
		for ( List<E> l : lists ) {
			l.toArray(buf);
			System.arraycopy(buf, 0, tmp, i, l.size());
			i += l.size();
		}
		return tmp;
	}
	
	class ChunkListIterator implements ListIterator<E> {
		// figure out list index
		final int idx;
		final int off;
		final int limit;
		
		int i;
		ListIterator<E> cur;
		
		ChunkListIterator(int from) {
			this(from,numElem);
		}
		
		ChunkListIterator(int from,int to) {
			idx = from / CHUNK_SIZE;
			off = from % CHUNK_SIZE;
			limit = Math.min(to / CHUNK_SIZE, lists.size() - 1);
			
			i = idx;
			cur = lists.get(idx).listIterator(off);
		}
		
		@Override
		public void add(E e) {
			throw new UnsupportedOperationException();
		}

		@Override
		public boolean hasNext() {
			if ( cur.hasNext() ) return true;
			if ( i >= limit ) return false; // we have no more elements
			cur = lists.get(++i).listIterator();
			return cur.hasNext();
		}

		@Override
		public boolean hasPrevious() {
			if ( cur.hasPrevious() ) return true;
			if ( i <= idx ) return false; // we have no more elements
			List<E> x = lists.get(--i);
			cur = x.listIterator(x.size()-1);
			return cur.hasPrevious();
		}

		@Override
		public E next() {
			return cur.next();
		}

		@Override
		public int nextIndex() {
			return cur.nextIndex() + i * CHUNK_SIZE;
		}

		@Override
		public E previous() {
			return cur.previous();
		}

		@Override
		public int previousIndex() {
			return cur.previousIndex() + i * CHUNK_SIZE;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

		@Override
		public void set(E e) {
			cur.set(e);
		}
	}
}
